package sword.T12;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-03-23 14:42:39 星期三
 */

class Solution {

    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};

    public boolean exist(char[][] board, String word) {
        if (word.length() == 0)
            return true;
        int m = board.length;
        int n = board[0].length;
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; ++j) {
                boolean res = search(board, i, j, word, 0);
                if (res)
                    return true;
            }
        }
        return false;
    }

    private boolean search(char[][] board, int x, int y, String word, int cur) {
        if (board[x][y] != word.charAt(cur))
            return false;
        if (cur == word.length()-1)
            return true;
        int m = board.length;
        int n = board[0].length;
        board[x][y] = 0;
        boolean flag = false;
        for (int i=0; i<4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                if (search(board, nx, ny, word, cur+1)) {
                    flag = true;
                    break;
                }
            }
        }
        board[x][y] = word.charAt(cur);
        return flag;
    }
}